package com.agile.leetcode.lru;


import java.util.HashMap;
import java.util.Map;

/**
 * 1. 实现思路
 * 目的是把最不常用的数据淘汰掉，所以需要记录一下每个元素的访问次数。最简单的方法就是把所有元素按使用情况排序，最近使用的，移到末尾。缓存满了，就从头部删除。
 * 2. 使用哪种数据结构实现？
 * 常用的数据结构有数组、链表、栈、队列，考虑到要从两端操作元素，就不能使用栈和队列。
 * 每次使用一个元素，都要把这个元素移到末尾，包含一次删除和一次添加操作，使用数组会有大量的拷贝操作，不适合。
 * 又考虑到删除一个元素，要把这个元素的前一个节点指向下一个节点，使用双链接最合适。
 * 链表不适合查询，因为每次都要遍历所有元素，可以和HashMap配合使用。
 * 双链表 + HashMap
 *
 * @Author:ChenZhangKun
 * @Date: 2021/11/15 11:11
 */
public class LruCache2<K, V> {
    public static void main(String[] args) {

    }
    private class Entry<K, V> {
        private K key;
        private V value;
        private Entry<K, V> before;
        private Entry<K, V> after;
    }

    private Integer capacity;
    // 头结点
    private Entry<K, V> head;
    // 尾节点
    private Entry<K, V> tail;
    // 起到一个方便查询的作用，头结点和尾节点维护lru
    private Map<K, Entry<K, V>> caches = new HashMap<>();

    public LruCache2(Integer capacity) {
        this.capacity = capacity;
    }

    public V get(K key) {
        // 拿到
        Entry<K, V> node = caches.get(key);
        if (node != null) {
            // 有访问，就移到链表末尾
            afterNodeAccess(node);
            return node.value;
        }
        return null;
    }

    private void afterNodeAccess(Entry<K, V> e) {
        Entry<K, V> last = tail;
        if (last != e) {
            // 断开与头结点的联系
            if (e.before == null) {
                // 头结点
                head = e.after;
            } else {
                // 不是头结点
                e.after.before = e.before;
            }
        }
        // 添加到尾节点
        if (last == null) {
            head = e;
        } else {
            e.before = last;
            last.after = e;
        }
        e.after = null;
        tail = e;
    }

    public V put(K key, V value) {
        Entry<K, V> entry = caches.get(key);
        if (entry == null) {
            entry = new Entry<K, V>();
            entry.key = key;
            entry.value = value;
            // 新节点添加到末尾
            linkNodeLast(entry);
            caches.put(key, entry);
            // 节点数大于容量，就删除头节点
            if (this.caches.size() > this.capacity) {
                this.caches.remove(head.key);
                afterNodeRemoval(head);
            }
            return null;
        }
        entry.value = value;
        // 节点有更新就移动到未节点
        afterNodeAccess(entry);
        caches.put(key, entry);
        return entry.value;
    }

    /**
     * 把该节点添加到尾节点
     */
    private void linkNodeLast(Entry<K, V> e) {
        final Entry<K, V> last = this.tail;
        // 头部是否为null
        if (head == null) {
            head = e;
        } else {
            e.before = last;
            last.after = e;
        }
        tail = e;
    }

    /**
     * 删除该节点
     */
    void afterNodeRemoval(Entry<K, V> e) {
        // 说明是头结点
        if (e.before == null) {
            // 头结点指向他的后一节点
            head = e.after;
        } else {
            e.before.after = e.after;
        }

        if (e.after == null) {
            tail = e.before;
        } else {
            e.after.before = e.before;
        }
    }
}
